package com.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
 *
 * 注意：
 *
 * 答案中不可以包含重复的四元组。
 *
 * 示例：
 *
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 *
 * 满足要求的四元组集合为：
 * [
 *   [-1,  0, 0, 1],
 *   [-2, -1, 1, 2],
 *   [-2,  0, 0, 2]
 * ]
 *
 * @author LiYongKui
 * @version 1.0
 * @date 2021/1/26 9:59
 */
public class Solution0018 {

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int len = nums.length;
        for (int a = 0; a <= (len - 4); a++) {
            if(a > 0 && nums[a] == nums[a-1]) {
                continue;
            }
            for (int b = a+1; b <= (len - 3); b++) {
                if(b > a+1 && nums[b] == nums[b-1]){
                    continue;
                }
                int c = b+1, d = len -1;
                while(c < d){
                    int tmp = nums[a] + nums[b] + nums[c] + nums[d];
                    if(tmp == target){
                        result.add(Arrays.asList(nums[a],nums[b],nums[c],nums[d]));
                        while(c<d && nums[c] == nums[c+1]) {
                            c++;
                        }
                        while(c<d && nums[d-1] == nums[d]) {
                            d--;
                        }
                        c++;
                        d--;
                    }else if(tmp > target){
                        d--;
                    }else if(tmp < target){
                        c++;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {0,0,0,0};
        System.out.println(fourSum(nums,0));
    }
}
